package com.duoduo.位运算;

/**
 * @program: algorithm
 * @description: 比特位计数338
 * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：[0,1,1]
 * 解释：
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 * @author: chaidl  ！
 * @create: 2022-04-30 21:23
 */
public class 比特位计数338 {
	// i & (i - 1)可以去掉i最右边的一个1（如果有），因此 i & (i - 1）是比 i 小的，而且i & (i - 1)的1的个数已经在前面算过了，所以i的1的个数就是 i & (i - 1)的1的个数加上1
	public int[] countBits(int n) {
		int[] bits=new int[n+1];
		bits[0]=0;
		for (int i = 1; i <= n; i++) {
			bits[i]=bits[i&(i-1)]+1;
		}
		return bits;
	}
}
